package com.atwy.graph.directedgraph;


/**
 * @Author: 小王子火
 * @Date: 2022/3/5
 * 邻接表表示有向图，一种链式存储
 * 包含两部分：
 * 1、顶点：包含顶点信息和指向第一个邻接点的指针
 * 2、邻接点：包含邻接点的存储下标和指向下一个邻接点的指针
 * <p>
 * 顶点Vj的所有邻接点构成一个单链表
 */
public class TableDigraph implements IDigraph{

    /**
     * 节点数、边数
     */
    int vexnum, edgenum;

    /**
     * VertexNode就是Bag
     */
    VertexNode<Integer> adjs[];
    /**
     * 顶点的邻接顶点的个数，有向图的顶点的出度
     */
    int[] vertexCount;

    public TableDigraph(int vexnum) {
        this.vexnum = vexnum;
        adjs = new VertexNode[vexnum];
        vertexCount = new int[vexnum];
        // 初始化所有链表
        for (int v = 0; v < vexnum; v++) {
            adjs[v] = new VertexNode<>();
        }
    }

    /**
     * 向图中添加一条边 v->w
     *
     * @param v
     * @param w
     */
    @Override
    public void addEdge(int v, int w) {
        adjs[v].add(new AdjNode(w));
        vertexCount[v]++;
        edgenum++;
    }
    @Override
    public int V() {
        return vexnum;
    }
    @Override
    public int E() {
        return edgenum;
    }

    /**
     * 返回由 v 指出的边所连接的所有顶点
     * @param v
     * @return
     */
    @Override
    public int[] adj(int v) {
        VertexNode<Integer> adj = adjs[v];
        AdjNode first = adj.first;
        int[] result = new int[vertexCount[v]];
        int count = 0;
        while (first!=null){
            result[count] = first.index;
            count++;
            first = first.next;
        }
        return result;
    }

    @Override
    public IDigraph reverse() {
        TableDigraph r = new TableDigraph(this.V());
        for (int v = 0; v < this.V(); v++) {
            for(int w : this.adj(v)){
                r.addEdge(w,v);
            }
        }
        return r;
    }

    /**
     * 顶点
     */
    public static class VertexNode<T> {
        /**
         * 顶点的数据类型
         */
        T data;
        /**
         * 顶点的邻接点
         */
        AdjNode first;

        public void add(AdjNode node) {
            if (first == null) {
                first = node;
            } else {
                // 头插法插入链表
                node.next = first;
                first = node;
            }
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder("VertexNode{");
            sb.append("data=").append(data);
            sb.append(", first=").append(first);
            sb.append('}');
            return sb.toString();
        }
    }

    /**
     * 邻接点
     */
    public static class AdjNode {
        /**
         * 邻接点的下标
         */
        int index;
        /**
         * 指向下一个邻接点
         */
        AdjNode next;

        public AdjNode() {
        }

        public AdjNode(int index) {
            this.index = index;
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder("AdjNode{");
            sb.append("index=").append(index);
            sb.append(", next=").append(next);
            sb.append('}');
            return sb.toString();
        }
    }

    public void print() {
        for (int v = 0; v < vexnum; v++) {
            System.out.print("V:" + v + ",adj->");
            AdjNode first = adjs[v].first;
            while (first != null) {
                System.out.print("[" + first.index + "]");
                first = first.next;
            }
            System.out.println();
        }
    }
}
